/*
 * @lc app=leetcode.cn id=452 lang=cpp
 *
 * [452] 用最少数量的箭引爆气球
 */

// @lc code=start
class Solution
{
    static bool cmp(const vector<int> &a, const vector<int> &b)
    {
        return a[0] < b[0];
    }

public:
    int findMinArrowShots(vector<vector<int>> &points)
    {
        //最少的箭引爆气球
        //实际上就是找最大的交集，如果集合之间存在交集就可以一起射爆
        //首先排序
        //我服了 这啥也没加 就一个循环都超时？
        //换成只用右终止位置 不用开始了
        //我真的服了 只用一个int它都能超时？？？
        //直接用vector计算 再超时这道题建议删除！
        //真超时了？？？？？
        //排序的时候cmp得改成引用 否则每次比较都要复制一份 耗时间
        sort(points.begin(), points.end(), cmp);
        int res = 1;
        for (int i = 1; i < points.size(); i++)
        {
            if (points[i][0] <= points[i-1][1])
            {
                //交集
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
            else
            {
                res++;
            }
        }
        return res;
    }
};
// @lc code=end
